/*
 * @lc app=leetcode.cn id=752 lang=swift
 *
 * [752] 打开转盘锁
 */

// @lc code=start
class Solution {
    func openLock(_ deadends: [String], _ target: String) -> Int {
        // 记录已经穷举过的密码，防止走回头路
        var q1 = Set<String>()
        var q2 = Set<String>()
        var visited = Set<String>()

        // 从起点开始启动广度优先搜索
        var step = 0
        q1.insert("0000")
        q2.insert(target)
        visited.formUnion(deadends)

        while !q1.isEmpty && !q2.isEmpty {
            // 将当前队列中的所有节点向周围扩散
            var temp = Set<String>()
            // 优化
            if q1.count > q2.count {
                var stemp = q1
                q1 = q2
                q2 = stemp
            }

            for cur in q1 {
                // 判断是否到达终点
                if visited.contains(cur) {
                    continue
                }
                if q2.contains(cur) {
                    return step
                }
                visited.insert(cur)

                // 将一个节点的未遍历相邻节点加入到队列
                for (index, char) in cur.enumerated() {
                    let currNumber: Int = Int(String(char))! //当前要拨动的***上的数字
                    let startIndex = cur.index(cur.startIndex, offsetBy: index)   //要拨动的数字反映在字符串中的范围
                    let endIndex = startIndex

                    // 向上拨
                    let upNumber: String = String((currNumber + 1) % 10)    //拨动后当前***的新数字
                    var upString: String = cur
                    upString.replaceSubrange(startIndex...endIndex, with: upNumber) //向上拨后的新***
                    temp.insert(upString)


                    // 向下拨
                    let downNumber: String = String((currNumber - 1 >= 0 ? currNumber - 1 : 9))
                    var downString: String = cur
                    downString.replaceSubrange(startIndex...endIndex, with: downNumber)
                    temp.insert(downString)
                }
            }

            step += 1
            q1 = q2
            q2 = temp
        }

        return -1
    }
}